1. dom-diff算法 | 砥砺前行

写作不易，Star是最大鼓励，感觉写的不错的可以给个Star⭐，请多多指教。本博客的Github地址。

diff算法原理

React将Virtual DOM树转换为actual DOM的最少操作过程称为调和（reconciliation）。

diff算法就是调和过程的具体实现。需要特别注意：render执行的结果得到的不是真正的DOM节点。结果仅仅是轻量级的JavaScript对象，我们称之为Virtual DOM。

diff算法的作用：计算出Virtual DOM中真正变化的部分，并只针对该部分进行原生DOM操作，而非重新渲染整个页面。

虚拟DOM

Virtual DOM，顾名思义就是虚拟节点。主要通过JS对象来模拟DOM中的节点，然后再通过render方法将其渲染成真实的DOM节点。

虚拟DOM实现

├── README.md
├── package.json
├── public
│   ├── favicon.ico
│   ├── index.html // 项目入口
│   ├── logo192.png
│   ├── logo512.png
│   ├── manifest.json
│   └── robots.txt
├── src
│   ├── diff.js
│   ├── element.js
│   ├── index.js // 主入口文件
│   └── patch.js
└── yarn.lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

上述项目目录结构是采用create-react-app脚手架直接生成的，目的是为了方便代码编译调试。

// 全局安装
yarn global add create-react-app
// 生成项目
create-react-app dom-diff
// 进入项目目录
cd dom-diff
// 启动项目
yarn run start

1
2
3
4
5
6
7
8

创建虚拟DOM

在element.js文件中主要实现如何创建虚拟DOM以及将创建出来的虚拟DOM渲染成真实的DOM。

代码如下：

// element.js
// 虚拟DOM元素的类
class Element {
    constructor(type, props, children) {
        // 将参数挂载到实例的私有属性上
        this.type = type;
        this.props = props;
        this.children = children;
    }
}
// 创建虚拟dom节点，返回object
function createElement(type, props, children) {
    return new Element(type, props, children);
}

export {
    Element,
    createElement
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在入口文件index.js里调用createElement方法来生成虚拟dom：

// index.js

// 首先引入对应的方法来创建虚拟DOM
import { createElement } from './element';

const virtualDom = createElement('ul', {class: 'list'}, [
    createElement('li', {class: 'item'}, ['科比']),
    createElement('li', {class: 'item'}, ['詹姆斯']),
    createElement('li', {class: 'item'}, ['罗斯'])
]);

console.log(virtualDom);

1
2
3
4
5
6
7
8
9
10
11
12

在Vue和React中用来创建虚拟DOM的方法也叫createElement。这里createElement方法接收三个参数，分别是type，props和children。

type: 指定dom元素的标签类型，如'ul'、'li'、'div'等；
props: 表示dom元素的属性，如class、style或者自定义属性；
children: 表示dom元素的子节点，元素可以拥有多个子节点，所以是一个数组。

生成的虚拟DOM如下图所示：

渲染虚拟DOM

// element.js
class Element {
    // 省略 同上文
}

function createElement() {
    // 省略 同上文
}
/**
 * 给DOM元素设置属性
 * @param  {any} node 当前dom元素
 * @param  {any} key 属性名称
 * @param  {any} value 属性值
 * @return {void}
 */
function setAttr(node, key, value) {
    switch (key) {
        // key是value的情况，需要判断是否为输入框
        case 'value': // node是一个input或者textarea
            if(node.tagName.toUpperCase() === 'INPUT' || node.tagName.toUpperCase() === 'TEXTAREA') {
                node.value = value;
            } else { // 其他情况直接调用setAttribute
                node.setAttribute(key, value);
            }
            break;
        case 'style':
            node.style.cssText = value; // 设置行内样式
            break;
        default: // 默认为普通属性，直接调用setAttribute赋值即可
            node.setAttribute(key, value);
            break;
    }
}
// render方法可以将vnode转化为真实dom
function render(eleObj) {
    const {type, props, children} = eleObj;
    // 调用createElement创建dom元素
    const el = document.createElement(type);
    for (let key in props) {
        // 给当前dom元素设置属性
        setAttr(el, key, props[key]);
    }
    // 遍历子节点，如果是虚拟dom继续渲染，不是就代表的是文本节点
    children.forEach(child => {
        // 判断当前子节点是否Element类型，是的话则为虚拟DOM节点，递归调用render方法渲染，否则返回一个文本节点
        child = (child instanceof Element) ? render(child) : document.createTextNode(child);
        el.appendChild(child);
    });
    return el;
}
// 将元素插入页面中
function renderDom(el, target) {
    target.appendChild(el);
}

export {
    Element,
    createElement,
    render,
    setAttr,
    renderDom
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

再次回到index.js文件中，调用render方法，代码如下：

import {
    createElement, // 创建虚拟DOM方法
    render,
    renderDom
} from './element';

const virtualDom = createElement('ul', {class: 'list'}, [
    createElement('li', {class: 'item'}, ['科比']),
    createElement('li', {class: 'item'}, ['詹姆斯']),
    createElement('li', {class: 'item'}, ['罗斯'])
]);

// console.log(virtualDom);
const el = render(virtualDom); // 将虚拟dom转化为了真实的dom
// console.log(el);
// window.root与document.querySelector('#root')等价
// 将渲染真实的dom添加到页面中
renderDom(el, window.root);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Diff策略

Web UI中DOM节点跨层级的移动操作很少，可以忽略不计；
拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构；
对于同一个层级的一组子节点，可以通过它们唯一的ID(uuid)来进行区分。

Diff粒度

Diff算法在执行时有三个维度，分别是Tree Diff、Component Diff和Element Diff，执行时按顺序依次执行，它们的差异仅仅因为Diff粒度不同、执行先后顺序不同。

Tree Diff

如上图所示：基于策略1，React对树的算法进行了简洁明了的优化。对树进行分层比较，两棵树只会对同一层次的节点进行比较。简单来讲就是：对树的每一层进行逐层遍历比较，如果组件不存在了则会直接删除。这样只需要对树进行一次遍历，便能完成整个DOM树的比较。

需要注意：整个diff过程中，只会对相同层级的DOM节点进行比较，不会跨层级比较。

React只会对相同层级的DOM节点进行比较，即同一个父节点下的所有子节点，当发现该节点已经不存在了，就会删除该节点和其所有子节点，不会再做进一步的比较。

而如果真的出现了跨层级的移动，并不会出现移动操作，而是被移动的根节点被删除后重新创建。

Component Diff

上图中，左边的根节点有A节点，右边的根节点没有A节点，在比较后，会直接删除A节点及其子节点B和C，在M节点下方重新生成A节点及其子节点B和C。

组件之间的比较策略：

如果是同一类型的组件，按原策略继续比较Virtual DOM树即可；
- 是否需要比较判断？对于同一类型的组件，可能其virtual DOM没有任何变化，如果能确切的知道这一点，那么就可以节省大量的diff运算时间。因此，React允许用户通过shouldComponentUpdate来判断是否需要对组件进行diff算法分析。
如果是不同类型的组件，则将该组件标记为dirty component，直接替换整个组件下的所有子节点，不需要浪费宝贵的时间去计算两个根本不可能相似的组件。

Element Diff

紧接着上述同一类型的组件，继续比较下去，常见类型：列表。

当节点处于同一个层级的时候，diff提供了三种节点操作：INSERT_MARKUP(插入)、MOVE_EXISTING(移动)、REMOVE_NODE(删除)。

比较策略：

使用uuid(即key)对列表组件命名；
先全部遍历一遍，确定要删除和新增的节点；
确定要删除的节点。
插入：新的节点不在旧的集合里，也就是是一个全新的节点；
旧集合中有新的组件类型，且element是可更新的类型，generateComponent-Children已经调用receiveComponent，这种情况下prevChild=nextChild，就需要做移动操作，可以复用以前的DOM节点；
旧组件类型，在新集合里也有，但对应的element不同则不能直接复用和更新，需要执行删除操作。或者旧组件不在新集合里，也要执行删除操作。

通过key来实现节点的移动。通过key发现新老集合中的节点都是相同的节点，因此无需进行节点删除和创建，只需要将老集合中节点的位置进行移动，更新为新集合中节点的位置。

具体分析

Tree Diff是对树的每一层进行遍历，如果某个组件不存在了，则会直接销毁。如上图所示：左边是老树，右边是新树，第一层是R组件，一模一样，不会发生变化；第二层进入Component Diff，同一类型组件继续比较下去，发现A组件没有，所以直接删掉A、B、C组件；继续第三层，重新创建A、B、C组件。

如上图所示：第一层遍历完，进行第二层遍历时，D和G组件是不同类型的组件，不同类型组件直接进行替换，将D删掉，再将G重建。

Element Diff紧接着以上统一类型组件继续比较下去，常见类型就是列表。同一个列表由旧变新有三种行为，插入、移动和删除，它的比较策略是对于每一个列表指定key，先将所有列表遍历一遍，确定要新增和删除的，再确定需要移动的。如上图所示：

第一步将D删掉；
第二步增加E；
剩下的A和B只需要移动位置即可。

DOM diff实现

DOM diff是比较两个虚拟dom的区别实际上就是比较两个对象的区别。 DOM diff作用：根据两个虚拟对象创建出补丁，描述改变的内容，将这个补丁用来更新dom。

DOM diff是通过js层面的计算，返回一个patch对象，即补丁对象。再通过特定的操作解析patch对象，完成页面的重新渲染。

差异计算

采用先序深度优先遍历。

用JS对象模拟虚拟DOM；
将虚拟DOM转化为真实的DOM并插入到页面中；
每当虚拟DOM发生变化的时候，比较新旧虚拟DOM之间的差异，得到一个差异对象(补丁包)；
根据补丁包对象对真实的DOM树打补丁，即更新DOM。

差异计算规则：

当老的DOM节点在新的虚拟DOM中不存在时，则移除；对应的补丁包对象为：{type: 'REMOVE', index}。
当文本节点的文本发生变化时，将新的文本节点值作为补丁包对象{type: 'TEXT', text: newNode}。
当新旧节点类型相同时，继续比较各个属性是否相同，产生一个属性的补丁包{type: 'ATTRS', attr: {class: 'list-group'}}。
当新旧节点类型不相同，直接产生一个替换的补丁包对象{type: 'REPLACE', newNode}。

// diff方法接收两个虚拟DOM
function diff(oldTree, newTree) {
    const patches = {};
    // 先遍历树的第一项
    let index = 0; // 标识树的节点索引
    // 递归树 比较后的结果放到补丁包中
    walk(oldTree, newTree, index, patches);
    return patches; // 最后将补丁包返回
}
// 定义一些常量来标识节点的变化类型，即补丁包对象的类型
const ATTRS = 'ATTRS'; // 节点属性发生变化
const TEXT = 'TEXT'; // 节点文本发生变化
const REMOVE = 'REMOVE'; // 删除节点
const REPLACE = 'REPLACE'; // 替换节点

let Index = 0; // 维护一个全局的节点索引，每次调用walk的时候都基于这个索引
/**
 * @param  {any} oldChildren 老节点的子节点
 * @param  {any} newChildren 新节点的子节点
 * @param  {any} patches 总的补丁包
 * @return {void}
 */
function diffChildren(oldChildren, newChildren, patches) {
    // 比较老的第一个和新的第一个
    // 这里需要循环oldChildren而不是newChildren，因为新节点的子节点有可能被删除了
    oldChildren.forEach((child, index) => {
        // 索引不应该是index了
        // 每次传递给walk时，index是递增的，所有元素都基于一个索引值来遍历
        walk(child, newChildren[index], ++Index, patches);
    });
}

// 字符串判断函数
function isString(node) {
    return Object.prototype.toString.call(node) === '[object String]';
}
/**
 * 节点属性不同的情况：
 * 1. 新老节点中都存在该属性，但是属性值发生了改变
 * 2. 新节点中找不到对应属性，说明该属性被删除了
 * 3. 老节点中找不到对应属性，说明该属性是新增的
 * @param  {any} oldAttrs
 * @param  {any} newAttrs
 * @return
 */
function diffAttr(oldAttrs, newAttrs) {
    const patch = {};
    // 判断老节点的属性和新节点的属性的关系
    // 先遍历老节点属性，找出发生改变的属性和被删除的节点
    for (let key in oldAttrs) {
        // 如果属性发生变化，放到补丁包对象中
        if (oldAttrs[key] !== newAttrs[key]) {
            // newAttrs[key]有可能是undefined，新的节点被删除了
            patch[key] = newAttrs[key];
        }
    }
    // 然后遍历新的节点属性，找出新增的属性
    for (let key in newAttrs) {
        // 如果老的节点属性中找不到相应属性，说明该属性为新增的
        if (!oldAttrs.hasOwnProperty(key)) {
            patch[key] = newAttrs[key];
        }
    }
    return patch;
}

// index被私有化到了walk作用域内
function walk(oldNode, newNode, index, patches) {
    // 存放当前节点的补丁对象
    const currentPatch = []; // 每个元素都有一个补丁对象
    if (!newNode) { // 当新节点被删除时
        // 记录哪个索引的节点被删除了
        currentPatch.push({type: REMOVE, index});
    }
    // 如果节点是字符串，说明是文本节点
    else if (isString(oldNode) && isString(newNode)) { // 判断文本节点内容是否发生变化
        if (oldNode !== newNode) {
            currentPatch.push({type: TEXT, text: newNode});
        }
    }
    else if (oldNode.type === newNode.type) { // 如果节点的类型相同，则比较节点的属性
        // 比较属性是否有更改，节点的props属性存放的是当前节点的所有属性
        const attrs = diffAttr(oldNode.props, newNode.props);
        // console.log(attrs);
        // length大于0说明当前节点属性发生了变化
        if (Object.keys(attrs).length > 0) {
            currentPatch.push({type: ATTRS, attrs})
        }
        // 如果当前节点存在子节点，继续递归遍历子节点(深度遍历)
        diffChildren(oldNode.children, newNode.children, patches);
    }
    else { // 上面情况都不满足，说明当前节点被替换了，即节点类型发生变化，比如由li变为div
        // 记录变化后的新的节点值，即newNode
        currentPatch.push({type: REPLACE, newNode});
    }
    // currentPatch.length大于0 说明当前元素发生了变化，确实有补丁
    if (currentPatch.length > 0) {
        // 将元素和补丁包对应起来，放到最终的补丁包中，index为当前节点的索引值
        patches[index] = currentPatch;
    }
}

export default diff;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

得到的补丁包对象如下图所示：

根据补丁对象更新DOM

import {
    render,
    Element
} from './element';
import {setAttr} from './element';

let allPatches;
let index = 0;
// node是真实dom，给真实dom打补丁
// patches是补丁对象
function patch(node, patches) {
    allPatches = patches;
    walk(node); // 给变化的元素打补丁
}

// 重新遍历老树，对变化的节点打补丁
function walk(node) {
    // 默认取出补丁包中的第一个补丁
    const currentPatch = allPatches[index++];
    // childNodes属性返回节点的子节点集合，是一个NodeList对象
    const childNodes = node.childNodes;
    // 当前节点有子节点的话，递归遍历子节点，即也是先序深度优先遍历
    // 子节点有补丁先给子节点打，最后给根节点打补丁
    childNodes.forEach(child => {
        walk(child);
    });
    if (currentPatch) {
        // 打补丁的顺序是逆序，先给子节点打，最后给根节点打
        doPatch(node, currentPatch);
    }
}

function doPatch(node, patches) {
    patches.forEach(patch => {
        switch (patch.type) {
            case 'ATTRS':
                for (let key in patch.attrs) {
                    const value = patch.attrs[key];
                    if (value) {
                        setAttr(node, key, value);
                    }
                    else { // 没有值，表示该属性不要了，直接删除
                        node.removeAttribute(key);
                    }
                }
                break;
            case 'TEXT':
                // textContent属性设置或者返回指定节点的文本内容
                node.textContent = patch.text;
                break;
            case 'REPLACE': // 节点替换
                // 如果新节点是一个Element，即虚拟DOM元素，需要先调用render方法将其渲染成真实的DOM
                const newNode = patch.newNode instanceof Element ? render(patch.newNode) : document.createTextNode(patch.newNode);
                node.parentNode.replaceChild(newNode, node);
                break;
            case 'REMOVE': // 节点删除
                node.parentNode.removeChild(node);
                break;
            default:
                break;
        }
    })
}

export default patch;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

// index.js
import {
    createElement, // 创建虚拟DOM方法
    render,
    renderDom
} from './element';
import diff from './diff';
import patch from './patch';

const virtualDom = createElement('ul', {class: 'list'}, [
    createElement('li', {class: 'item'}, ['科比']),
    createElement('li', {class: 'item'}, ['詹姆斯']),
    createElement('li', {class: 'item'}, ['罗斯'])
]);

const virtualDom2 = createElement('ul', {class: 'list-group'}, [
    createElement('li', {class: 'item'}, ['韦德']),
    createElement('li', {class: 'item'}, ['詹姆斯']),
    createElement('div', {class: 'item'}, ['库里'])
]);

// console.log(virtualDom);
const el = render(virtualDom);
console.log(el);
// window.root与document.querySelector('#root')等价
// 将虚拟dom转化为了真实的dom，并添加到页面中
renderDom(el, window.root);

// 通过diff算法产生一个补丁对象
const patches = diff(virtualDom, virtualDom2);
console.log(patches);
// 给元素打补丁，重新更新视图
patch(el, patches);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

运行代码，在浏览器里看到DOM被更新了，如下图所示：

页面绘制

批量操作

当你在一个组件上调用其setState方法时，React会将其标记为dirty。然后在本次事件循环结束时，React会查找dirty的组件并将其重新绘制。

这就意味着不论有多少此setState操作，React都只会在事件循环结束时批量更新DOM。这就是React高性能的关键。用通用js方法来实现这种批量更新是很麻烦的，而React默认会帮你搞定这些。

子树重绘

当组件的setState方法被调用时，组件会重新构建它的子节点。如果你在根元素上调用了setState方法，那么整个App都会被重绘。所有的组件的render方法都会被调用，即使它们并没有改变。虽然这听起来很吓人，好像很不高效。但实际上还可以，因为它根本没有修改真正的DOM。

首先，让我们讨论下UI界面的展示。因为空间是有限的，我们通常会同时按照顺序显示成百上千个元素。Javascript已经足够快了，完全可以hold住普通的业务逻辑需求。

另外一个重要点是，当你写React代码时不要经常调用root节点的setState方法来修改东西。你可以在触发事件的组件或是其父组件上调用setState方法。通常你不需要调用root的setState方法。这意味着你需要将UI改变控制在用户交互触发的区域。

优化子树的绘制

你可以控制是否阻止子树的重绘，只需要覆盖组件的方法即可，方法如下：

boolean shouldComponentUpdate(objectnextProps, objectnextState)

通过对比组件前后的props和state，你就可以判断这个组件是否真的有必要重绘。只要实现妥当，会大大提升性能。

为了实现这个对比，你就需要对比Javascript对象。这会遇到很多问题，例如对象的对比是深度对比还是仅仅做浅层对比？如果我们用的深度对比，那么是应该使用不可变的（immutable）数据机构还是做深度拷贝呢？

还有一件事情你需要记住：shouldComponentUpdate函数会经常被调用，所以一定要确保你实现的函数比绘制组件所需要的时间更少。不然就没有优化的价值了。

总结

React通过制定大胆的diff策略，将O(n3)复杂度的问题转换成 O(n)复杂度的问题；
React通过分层求异的策略，对tree diff进行算法优化；
React通过相同类生成相似树形结构，不同类生成不同树形结构的策略，对component diff进行算法优化；
React通过设置唯一key的策略，对element diff进行算法优化；
建议在开发组件时，保持稳定的DOM结构会有助于性能的提升；
建议在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，在一定程度上会影响React的渲染性能。

参考文档

← 首页 2. Redux源码分析→

# diff算法原理

# 虚拟DOM

# 虚拟DOM实现

# 创建虚拟DOM

# 渲染虚拟DOM

# Diff策略

# Diff粒度

# Tree Diff

# Component Diff

# Element Diff

# 具体分析

# DOM diff实现

# 差异计算

# 根据补丁对象更新DOM

# 页面绘制

# 批量操作

# 子树重绘

# 优化子树的绘制

# 总结

# 参考文档

diff算法原理

虚拟DOM

虚拟DOM实现

创建虚拟DOM

渲染虚拟DOM

Diff策略

Diff粒度

Tree Diff

Component Diff

Element Diff

具体分析

DOM diff实现

差异计算

根据补丁对象更新DOM

页面绘制

批量操作

子树重绘

优化子树的绘制

总结

参考文档